#include <stdio.h>
#include <stdlib.h>

//归并排序
/*
通常采用二路归并
把数组中两个有序的序列归并为一个


*/

//将两个各自有序的序列归并
void Merge(int A[], int low, int mid, int high)
{
    int i, j, k;
    int *B;
    for (k = low; k <= high; k++)
    {
        B[k] = A[k];
    }
    for (i = low, j = mid + 1, k = i; i < mid && j < high; k++)
    {
        if (B[i] <= B[j])
        {
            A[k] = B[i++];
        }
        else
        {
            A[k] = B[j++];
        }
    }
    while (i <= mid)
    {
        A[k++] = B[j++];
    }
    while (j <= high)
    {
        A[k++] = B[j++];
    }
}

void MergeSort(int A[], int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2; //从中间拆分
        MergeSort(A, low, mid);     //对左半部分归并排序
        MergeSort(A, mid, high);    //对右半部分归并排序
        Merge(A, low, mid, high);   //归并
    }
}

/*
可以把整个归并的过程看做一颗倒立的二叉树（归并树）

时间复杂度 O(nlog n)
空间复杂度：O(n)
稳定的

*/

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}